package com.ywgt;

public class Prim {
    static final int N=1000;
    public static void main(String[] args) {
        char[] points={'A','B','C','D','E','F','G'};
        int [][] diatance=new int[points.length][points.length];
        diatance[0]=new int[]{N,5,7,N,N,N,2};
        diatance[1]=new int[]{5,N,N,9,N,N,3};
        diatance[2]=new int[]{7,N,N,N,8,N,N};
        diatance[3]=new int[]{N,9,N,N,N,4,N};
        diatance[4]=new int[]{N,N,8,N,N,5,4};
        diatance[5]=new int[]{N,N,N,4,5,N,6};
        diatance[6]=new int[]{2,3,N,N,4,6,N};
        MGraph mGraph=new MGraph(points,diatance);
        mGraph.print();
        mGraph.creteMinTree(0);
    }
}
class MGraph{
    char[] point;
    int [] [] weight;
    boolean [] isVisited;

    public MGraph(char[] points,int [][]dis) {
        point=points;
        weight=dis;
        isVisited=new boolean[point.length];
    }

    /**
     * 从第几个点开始生成最小树
     * @param v
     */
    public void creteMinTree(int v){
        //先将传进来的节点转为被访问
        isVisited[v]=true;
        //定义节点指针
        int pre=-1;
        int last=-1;
        //定义最小的权值
        int min=1000;
        for (int i = 1; i < point.length; i++) { //一共要生成point.length-1条边，可以生成树，每次循环生成一条
            for (int j = 0; j < point.length; j++) { //根据当前已被访问的节点，循环访问所有点
                for (int k = 0; k < point.length; k++) {
                    //如果有连接并且没有被访问过的的点，并且权值比较小将最小权值修改
                    if(isVisited[j]&&!isVisited[k]&&weight[j][k]<min){
                        min=weight[j][k];
                        pre=j;
                        last=k;
                    }
                }
            }
            System.out.println(point[pre]+"->"+point[last]+"权值"+weight[pre][last]);
            isVisited[last]=true;
            min=1000;
        }

    }

    public void print(){
        for (int i = 0; i < weight.length; i++) {
            for (int j = 0; j < weight[i].length; j++) {
                System.out.print(weight[i][j]+"\t");
            }
            System.out.println();
        }
    }
}
